package Exercise;


import java.util.Stack;

/**
 * Description：
 * Author: zhangc
 * Date：2017/9/7 9:15
 */
public class SingleStackDemo {


    private static class SingleStack {
        private int pre;
        private int last;

        public int getPre() {
            return pre;
        }

        public void setPre(int pre) {
            this.pre = pre;
        }

        public int getLast() {
            return last;
        }

        public void setLast(int last) {
            this.last = last;
        }

        @Override
        public String toString() {
            return "SingleStack{" +
                    "pre=" + pre +
                    ", last=" + last +
                    '}';
        }
    }

    /**
     * 单调栈，求一个数组中每个元素离他最近的比他小的数的位置
     * 此函数要求不能有 重复元素
     *
     * @param arr
     * @return
     */
    public static SingleStack[] getSingleStack(int[] arr) {
        SingleStack[] stacks = new SingleStack[ arr.length ];
        Stack<Integer> stack = new java.util.Stack<>();
        SingleStack singleStack = null;
        for (int i = 0; i < arr.length; i++) {
            if (stack.isEmpty())
                stack.push(i);
            else if (arr[ i ] > arr[ stack.peek() ])
                stack.push(i);
            else {
                singleStack = new SingleStack();
                stacks[ stack.peek() ] = singleStack;
                singleStack.setLast(i);
                stack.pop();
                singleStack.setPre(stack.isEmpty() ? -1 : stack.peek());
                --i;
            }
        }
        while (!stack.isEmpty()) {
            singleStack = new SingleStack();
            stacks[ stack.peek() ] = singleStack;
            singleStack.setLast(-2);
            stack.pop();
            singleStack.setPre(stack.isEmpty() ? -1 : stack.peek());
        }
        return stacks;
    }


    /**
     * 单调栈，求一个数组中每个元素离他最近的比他小的数的位置
     * 此函数可以有 重复元素
     *
     * @param arr
     * @return
     */
    public static SingleStack[] getSingleStackAllowRepeat(int[] arr) {
        SingleStack[] stacks = new SingleStack[ arr.length ];
        Stack<Integer> stack = new java.util.Stack<>();
        SingleStack singleStack = null;
        for (int i = 0; i < arr.length; i++) {
            if (stack.isEmpty())
                stack.push(i);
            else if (arr[ i ] > arr[ stack.peek() ])
                stack.push(i);
            else if (arr[ i ] == arr[ stack.peek() ]) {
                singleStack = new SingleStack();
                stacks[ i ] = singleStack;
                stacks[ stack.peek() ] = singleStack;
                stack.pop();
                stack.push(i);
            } else {
                singleStack = stacks[ stack.peek() ] == null ? new SingleStack() : stacks[ stack.peek() ];
                stacks[ stack.peek() ] = singleStack;
                singleStack.setLast(i);
                stack.pop();
                singleStack.setPre(stack.isEmpty() ? -1 : stack.peek());
                --i;
            }
        }
        while (!stack.isEmpty()) {
            singleStack = stacks[ stack.peek() ] == null ? new SingleStack() : stacks[ stack.peek() ];
            if (stacks[ stack.peek() ] == null)
                stacks[ stack.peek() ] = singleStack;
            singleStack.setLast(-2);
            stack.pop();
            singleStack.setPre(stack.isEmpty() ? -1 : stack.peek());
        }
        return stacks;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 4, 5, 2, 6};
        SingleStack[] singleStack = getSingleStackAllowRepeat(arr);
        SingleStack single;
        for (int i = 0; i < singleStack.length; i++) {
        }
    }

}
